﻿// 4941. 凑数.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>

/*
https://www.acwing.com/problem/content/4944/

初始时，n=0
。

每一轮操作都要依次完成两个步骤：

第一步，任选一个非负整数 a
，将 n
 增加 a
，这一步所需付出的代价为 a
。
第二步，将 n
 乘以 2
，这一步无需付出任何代价。
你可以不断重复上述操作。

给定一个整数 x
，你的任务是使 n
 在某一步操作后（不一定是某一轮结束后）恰好等于 x
 且付出的总代价尽可能少。

请你计算，为了完成任务所需付出的最小总代价。

例如，如果 x=5
，则最佳操作方案为：

第 1
 轮操作中，第一步，将 n
 增加 1
（付出代价 1
），使得 n
 变为 1
，第二步，将 n
 乘以 2
，使得 n
 变为 2
。
第 2
 轮操作中，第一步，将 n
 增加 0
（付出代价 0
），则 n
 仍然为 2
，第二步，将 n
 乘以 2
，使得 n
 变为 4
。
第 3
 轮操作中，第一步，将 n
 增加 1
（付出代价 1
），使得 n
 变为 5
。此时 n
 等于 x
 成立，任务完成。
付出的最小总代价为 2
。
再例如，如果 x=8
，则最佳操作方案为：

第 1
 轮操作中，第一步，将 n
 增加 1
（付出代价 1
），使得 n
 变为 1
，第二步，将 n
 乘以 2
，使得 n
 变为 2
。
第 2
 轮操作中，第一步，将 n
 增加 0
（付出代价 0
），则 n
 仍然为 2
，第二步，将 n
 乘以 2
，使得 n
 变为 4
。
第 3
 轮操作中，第一步，将 n
 增加 0
（付出代价 0
），则 n
 仍然为 4
，第二步，将 n
 乘以 2
，使得 n
 变为 8
。此时 n
 等于 x
 成立，任务完成。
付出的最小总代价为 1
。
输入格式
一个整数 x
。

输出格式
一个整数，表示所需付出的最小总代价。

数据范围
前 3
 个测试点满足 1≤x≤10
。
所有测试点满足 1≤x≤109
。

输入样例1：
5
输出样例1：
2
输入样例2：
8
输出样例2：
1
*/
int main()
{
    std::cout << "Hello World!\n";
}
 